import functools
class Solution(object):
    def diffWaysToCompute(self, expression):
        """
        :type expression: str
        :rtype: List[int]
        """
        if expression[0] == '-':
            op = ['-']
            left_index = 1
        else:
            op = ['+']
            left_index = 0
        nums = []
        right_index = left_index
        n = len(expression)
        while right_index < n:
            if expression[right_index] in {'+', '-', '*'}:
                nums.append(int(expression[left_index: right_index]))
                op.append(expression[right_index])
                left_index = right_index + 1
            right_index += 1
        nums.append(int(expression[left_index: right_index]))
        count = len(nums)
        @functools.cache
        def search(i, j):
            if j - i == 0:
                return [nums[i]]
            now = []
            for k in range(i, j):
                first = search(i, k)
                secound = search(k + 1, j)
                for f in first:
                    for s in secound:
                        if op[k + 1] == '+':
                            now.append(f + s)
                        if op[k + 1] == '*':
                            now.append(f * s)
                        if op[k + 1] == '-':
                            now.append(f - s)
            return now

        return search(0, count - 1)






data = Solution()
expression = "2*3-4*5"
print(data.diffWaysToCompute(expression))
